Resources

Question Source: https://leetcode.com/problems/validate-ip-address/

Iterative: O(n) / O(n)

Intuition

We can parse the provided IP and see if it fulfills the validation rules. A simple way to do this is to split the IP based on deliminators : or . and then check the split sections to see if they fit into IPv4 or IPv6 rules.

Big-O Analysis

The runtime is O(n) because we have to do a few operations that all require O(n) time. See comments in the code. For an overview of time complexities in Python, see Python Wiki

The space is O(n) because we must split string into an array of strings, and that array can have O(n) space in the worst case. This can actually be optimized to O(1) as shown below.

Code

Note:

isdigit() and isnumeric() can both be used. To understand the difference, see this article.
try... except... is used, but this should be optimized (see second solution below)
sections with * are actually redundant. We check if the str can be turned into a hexadecimal, which means it must be alphanumeric

class Solution:
    def validIPAddress(self, IP):
        IP_type = None
        # Check if close to IPv4 or IPv6 format: O(n) / O(1) for x in s
        if "." in IP:
            IP_type = "IPv4"
        elif ":" in IP:
            IP_type = "IPv6"
        else:
            return "Neither"
        print(IP_type)

        if IP_type == "IPv4":
            # split into array: O(n) / O(n)
            split = IP.split(".")
            # must have 4 sections: O(1) / O(1)
            if len(split) != 4:
                return "Neither"
            
            for i in range(len(split)):
                # length can't be more than 3 or 0: O(1) / O(1) for len()
                if len(split[i]) > 3 or len(split[i]) == 0: 
                    return "Neither" 
                # check if number: O(n) / O(1) (not sure about space)
                if not split[i].isnumeric(): #
                    return "Neither"
                # check for leading zero: O(1) / O(1)
                if split[i][0] == "0" and len(split[i]) > 1:
                    return "Neither"
                # convert str to int: O(n) / O(1)
                split[i] = int(split[i])
                # check if number is 255 or less: O(1) / O(1)
                if split[i] > 255:
                    return "Neither"
            return "IPv4"

        elif IP_type == "IPv6":
            split = IP.split(":")
            # must have 8 sections: O(n) / O(1) for x in s
            if len(split) != 8:
                return "Neither"

            for i in range(len(split)):
                # length can't be more than 4 or 0: O(1) / O(1) for len()
                if len(split[i]) > 4 or len(split[i]) == 0:
                    return "Neither"
                # check if numbers and letters only: O(n) / O(1)*
                if not split[i].isalnum():
                    return "Neither"
                # must be hexadecimal*
                try:
                    # O(n) / O(1) (not sure about space)
                    a = int(split[i],16)
                except:
                    return "Neither"

            return "IPv6"

s = Solution()
print(s.validIPAddress("192.0.0.1"))  # Neither - more than four sections
print(s.validIPAddress("12.12.12.12.12"))  # Neither - more than four sections
print(s.validIPAddress("172.16.254.01")) # Neither - leading zerop
print(s.validIPAddress("172.16.256.1")) # Neither - over 255
print(s.validIPAddress("172.16.254.a")) # Neither - not numeric
print(s.validIPAddress("172.16.254.1")) # IPv4
print(s.validIPAddress("2001:0db8:85a3:0:0:8A2E::7334")) # Neither - empty section
print(s.validIPAddress("2001:0db8:85a3:0:0:8A$$:0370:7334")) # Neither - not alphanumeric
print(s.validIPAddress("2001:0db8:85a3:0000"))  # Neither - less than 8 sections
print(s.validIPAddress("2001:0db8:85G3:0000"))  # Neither - not hexadecimal
print(s.validIPAddress("2001:0db8:85a3:0000:0000:8a2e:0370:7334"))  # IPv6

Iterative: O(n) / O(1)

Here we refactor the above code as follows:

reduce if, else statements by creating new class methods
reduce space by checking upfront wether the number of sections are correct for IPv4 or IPv6. This allows the split() operation to become constant space because we always end up with an array of length 4 or 8.
replace try... except... with different logic
use isdigit() instead of isnumeric()
instead of using an index in the for loop, we can use the element directly
combine some if statements
instead of converting each element in the array to an int, we can check directly in the if statement
remove the redundant section

class Solution:
    def validIPAddress(self, IP):
        if IP.count(".") == 3:
            return    self.checkIPv4(IP)
        elif IP.count(":") == 7:
            return self.checkIPv8(IP)
        else:
            return "Neither"
    
    def checkIPv4(self, IP):
        # this new array is constant size of 4
        array = IP.split(".")
        for e in array:
            # length can't be more than 3 and must be a number less than or equal to 255
            if len(e) > 3 or not e.isdigit() or int(e) > 255:
                return "Neither" 
            # check for leading zero
            if e[0] == "0" and len(e) > 1:
                return "Neither"
        return "IPv4"

    def checkIPv8(self, IP):
        # this new array is constant size of 8
        array = IP.split(":")
        hex_vals = "0123456789abcdefABCDEF"
        # validate each element "e" in array
        for e in array:
            # length can't be more than 4 or 0
            if len(e) > 4 or len(e) == 0:
                return "Neither"
            # check if hex_valsademical for each characer "c" in e
            for c in e:
                if c not in hex_vals:
                    return "Neither"
        return "IPv6"

s = Solution()
print(s.validIPAddress("192.0.0.1"))  # Neither - more than four sections
print(s.validIPAddress("12.12.12.12.12"))  # Neither - more than four sections
print(s.validIPAddress("172.16.254.01")) # Neither - leading zerop
print(s.validIPAddress("172.16.256.1")) # Neither - over 255
print(s.validIPAddress("172.16.254.a")) # Neither - not numeric
print(s.validIPAddress("172.16.254.1")) # IPv4
print(s.validIPAddress("2001:0db8:85a3:0:0:8A2E::7334")) # Neither - empty section
print(s.validIPAddress("2001:0db8:85a3:0:0:8A$$:0370:7334")) # Neither - not alphanumeric
print(s.validIPAddress("2001:0db8:85a3:0000"))  # Neither - less than 8 sections
print(s.validIPAddress("2001:0db8:85G3:0000"))  # Neither - not hexadecimal
print(s.validIPAddress("2001:0db8:85a3:0000:0000:8a2e:0370:7334"))  # IPv6